/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */

class Solution
{
public:
    ListNode *middleNode(ListNode *head)
    {
        // int length = 0;
        // ListNode *node = head;
        // while (node != nullptr)
        // {
        //     ++length;
        //     node = node->next;
        // }
        // int half_len = length / 2;
        // node = head;
        // for (int i = 0; i < half_len; ++i)
        // {
        //     node = node->next;
        // }
        // return node;
        ListNode *slow = head;
        ListNode *fast = head;
        while (true)
        {
            if (fast == nullptr)
            {
                return slow;
            }
            if (fast->next == nullptr)
            {
                return slow;
            }
            fast = fast->next->next;
            slow = slow->next;
        }
    }
};